package myList2;

class DLinkNode<T>            //双链表结点泛型类
{
    T data;                //结点元素值
    DLinkNode<T> prior;        //前驱结点指针
    DLinkNode<T> next;            //后继结点指针

    public DLinkNode()            //构造方法
    {
        prior = null;
        next = null;
    }

    public DLinkNode(T d)        //重载构造方法
    {
        data = d;
        prior = null;
        next = null;
    }
}

public class MyDLinkedList<T>        //双链表泛型类
{
    DLinkNode<T> dhead;            //存放头结点

    public MyDLinkedList()            //构造方法
    {
        dhead = new DLinkNode<T>();        //创建头结点
        dhead.prior = null;
        dhead.next = null;
    }

    //基本运算算法
    private DLinkNode<T> getIndex(int i)            //返回序号为i的结点
    {
        DLinkNode<T> p = dhead;
        int j = -1;
        while (j < i) {
            j++;
            p = p.next;
        }
        return p;
    }

    public int size()                            //求线性表长度
    {
        DLinkNode<T> p = dhead;
        int cnt = 0;
        while (p.next != null)                    //找到尾结点为止
        {
            cnt++;
            p = p.next;
        }
        return cnt;
    }

    public void createListF(T[] a)    //头插法：由数组a整体建立双链表
    {
        DLinkNode<T> s;
        for (int i = 0; i < a.length; i++)    //循环建立数据结点s
        {
            s = new DLinkNode<T>(a[i]);    //新建存放a[i]的结点s，插到表头
            s.next = dhead.next;        //修改s结点的next成员
            if (dhead.next != null)        //修改头结点的非空后继结点的prior
                dhead.next.prior = s;
            dhead.next = s;            //修改头结点的next成员
            s.prior = dhead;            //修改s结点的prior成员
        }
    }

    public void createListR(T[] a)    //尾插法：由数组a整体建立双链表
    {
        DLinkNode<T> s, t;
        t = dhead;                //t始终指向尾结点
        for (int i = 0; i < a.length; i++)    //循环建立数据结点s
        {
            s = new DLinkNode<T>(a[i]);    //新建存放a[i]元素的结点s
            t.next = s;            //将s结点插入t结点之后
            s.prior = t;
            t = s;
        }
        t.next = null;            //将尾结点的next成员置为null
    }

    public void delete(int i)        //在线性表中删除序号i位置的元素
    {
        if (i < 0 || i > size() - 1)        //参数错误抛出异常
            throw new IllegalArgumentException("删除:位置i不在有效范围内");
        DLinkNode<T> p = getIndex(i);        //找到序号为i的结点p,删除该结点
        if (p.next != null)            //修改p结点非空后继结点的prior
            p.next.prior = p.prior;
        p.prior.next = p.next;        //修改p结点的前驱结点的next
    }

    public void insert(int i, T e)    //在线性表中序号i位置插入元素e
    {
        if (i < 0 || i > size())        //参数错误抛出异常
            throw new IllegalArgumentException("插入:位置i不在有效范围内");
        DLinkNode<T> s = new DLinkNode<T>(e);    //建立新结点s
        DLinkNode<T> p = getIndex(i - 1);        //找序号为i-1结点p,其后插入s结点
        s.next = p.next;            //修改s结点的next成员
        if (p.next != null)            //修改p结点的非空后继结点的prior
            p.next.prior = s;
        p.next = s;                //修改p结点的next成员
        s.prior = p;                //修改s结点的prior成员
    }


    public void add(T e)                        //在线性表的末尾添加一个元素e
    {
        DLinkNode<T> s = new DLinkNode<T>(e);        //新建结点s
        DLinkNode<T> p = dhead;
        while (p.next != null)                    //查找尾结点p
            p = p.next;
        p.next = s;                                //在尾结点之后插入结点s
        s.prior = p;
    }

    public void setSize(int nlen)                //设置线性表的长度
    {
        int len = size();
        if (nlen < 0 || nlen > len)
            throw new IllegalArgumentException("设置长度:n不在有效范围内");
        if (nlen == len) return;
        DLinkNode<T> p = getIndex(nlen - 1);            //找到序号为nlen-1的结点p
        p.next = null;                            //将结点p置为尾结点
    }

    public T getElem(int i)                        //返回线性表中序号为i的元素
    {
        int len = size();
        if (i < 0 || i > len - 1)
            throw new IllegalArgumentException("查找:位置i不在有效范围内");
        DLinkNode<T> p = getIndex(i);                    //找到序号为i的结点p
        return p.data;
    }

    public void setElem(int i, T e)                //设置序号i的元素为e
    {
        if (i < 0 || i > size() - 1)
            throw new IllegalArgumentException("设置:位置i不在有效范围内");
        DLinkNode<T> p = getIndex(i);                    //找到序号为i的结点p
        p.data = e;
    }

    public int getNo(T e)                        //查找第一个为e的元素的序号
    {
        int j = 0;
        DLinkNode<T> p = dhead.next;
        while (p != null && !p.data.equals(e)) {
            j++;                                //查找元素e
            p = p.next;
        }
        if (p == null)                            //未找到时返回-1
            return -1;
        else
            return j;                            //找到后返回其序号
    }

    public String toString()                    //将线性表转换为字符串
    {
        String ans = "";
        DLinkNode<T> p = dhead.next;
        while (p != null) {
            ans += p.data + " ";
            p = p.next;
        }
        return ans;
    }
}

